最长有效括号

2024-07-06 18:36| 来源: 网络整理| 查看: 265

最长有效括号概况

标签：Dynamic-programming String Array 难度：★★★ 评分：★★★★★ 原题：中文 / 英文

描述

给定一个只包含 '('和 ')'的字符串，找出最长的包含有效括号的子串的长度。

示例1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"Description

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"最长的合格括号串长度解法

左括号序号入栈, 遇到右括号, 看栈顶是否匹配, 匹配则弹出栈顶, 否则右括号序号入栈. 最终栈中存着非法括号的序号, 他们将整个字符串分割成一段段合法的子串. 分别根据这些非法字符计算中间分割的子串的长度, 并记录最长的一个. 注意最后一个串长度的计算.

class Solution { public: int longestValidParentheses(string str) { unordered_map match = { {')', '('}, {']', '['}, {'}', '{'} }; stack s; s.push(-1); for (int i = 0; i

【本文地址】

公司简介

联系我们